#include <bits/stdc++.h>

using namespace std;

// 买卖股票的最佳时机含手续费
// 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格
// 整数 fee 代表了交易股票的手续费用
// 你可以无限次地完成交易，但是你每笔交易都需要付手续费
// 如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
// 返回获得利润的最大值
// 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

class Solution 
{
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        // prepare : 交易次数无限制情况下，获得收益的同时扣掉了一次购买和手续费之后，最好的情况
        int prepare = -prices[0] - fee;
        // done : 交易次数无限制情况下，能获得的最大收益
        int done = 0;
        int n = prices.size();
        for(int i = 1; i < n; ++i)
        {
            // done : 第i天不卖出股票，延续前一天的状态
            // prepare + prices[i] ：第i天卖出股票
            done = max(done, prepare + prices[i]);
            // prepare ：第i天不买入股票，延续前一天的状态
            // done - prices[i] - fee ：第i天买入股票
            prepare = max(prepare, done - prices[i] - fee);
        }
        return done;
    }
};


class Solution 
{
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        int n = prices.size();
        // f[i] : 第i天持有股票时的最大利润
        // g[i] : 第i天不持有股票时的最大利润
        // 手续费统一在卖出股票时进行扣除
        int f[n], g[n];
        f[0] = -prices[0], g[0] = 0;
        for(int i = 1; i < n; ++i)
        {
            // f[i - 1] ：延续前一天的状态
            // g[i - 1] - prices[i] ：第i天买入股票
            f[i] = max(f[i - 1], g[i - 1] - prices[i]);
            // g[i - 1] ：延续前一天的状态
            // f[i - 1] - fee + prices[i] ：第i天卖出股票并扣除手续费
            g[i] = max(g[i - 1], f[i - 1] - fee + prices[i]);
        }
        return g[n - 1];
    }
};